# -*- coding=utf-8 -*-
# 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置
# 你的算法时间复杂度必须是 O(log n) 级别
# 如果数组中不存在目标值，返回 [-1, -1]

# 示例 1:
# 输入: nums = [5,7,7,8,8,10], target = 8
# 输出: [3,4]

# 示例 2:
# 输入: nums = [5,7,7,8,8,10], target = 6
# 输出: [-1,-1]

# 一遍通过，超过100%，高兴，嘻嘻嘻！！！
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        l_result = r_result = self.search(nums, 0, len(nums), target);
        while l_result - 1 >= 0:
            result = self.search(nums, 0, l_result, target);
            if result == -1:
                break;
            l_result = result;
        while r_result + 1 <= len(nums) - 1:
            result = self.search(nums, r_result + 1, len(nums), target);
            if result == -1:
                break;
            r_result = result;

        return [l_result, r_result];

    # [begin, end)
    def search(self, nums, begin, end, target):
        l = begin;
        r = end - 1;
        while l <= r:
            helf = (l + r) / 2;
            if nums[helf] == target:
                return helf;
            if nums[helf] > target:
                r = helf - 1;
            else:
                l = helf + 1;
        return -1;

t = Solution();
print t.searchRange([], 8);